package com.structure.algorithm;

/**
 * 合并多个有序的列表，可以参考归并排序
 * 合并思路和双列表一样
 * Created by sucre on 2015/12/1.
 */
public class MergeKList {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists ==null || lists.length ==0){
            return null;
        }
        //这也是一种解法，但是超过要求的时间了，也就是说时间杂度太大了，所以不可取
        /*ListNode dummy = new ListNode(0);
        ListNode ln = null;
        for(int i=0;i<lists.length;i++){
            ln = mergeTwoLists(dummy,lists[i]);
        }
        return ln;*/
        /**
         * 第二种方法，这种方法的好处是很省空间，因为是在原数组上进行操作的
         * 将两个数组中的值合并后放到前一个数组元素中，例如：0、1位元素合并，将
         * 结果放到0里面，2、3元素合并将结果放到1里面，执行的次数是总长度的一半
         * 如果长度为奇数还需要另外考虑多出来的元素。
         * 其实还有一种方法，如果题目给出的是List<ListNode> lists,那么我们的解决方法是
         * 见MergeKListII
         */
        int size = lists.length;
        while(size > 1){
            for (int i=0;i<size/2;i++){
                lists[i] = mergeTwoLists(lists[i*2],lists[i*2+1]);
            }
            if((size & 1)==1){
                lists[size/2 -1] = mergeTwoLists(lists[size/2 -1],lists[size -1]);
            }
            size = size/2;
        }
        return lists[0];
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建一个为0的节点，其它节点放到它的next位上
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        //两个不能都存在时进入
        while(l1!=null && l2 !=null){
            //判断当前节点值的大小
            if(l1.val <= l2.val){
                //将大的列表当前节点的值赋给pre.next
                pre.next = l1;
                //这一步很关键，要将当前列表的其它节点顺次前移
                l1 = l1.next;
            }else{
                pre.next = l2;
                l2 = l2.next;
            }
            //这一步很关键，pre.next的地址赋给pre,使得pre始终保持单节点，这样有利于l1或l2节点的值合并到pre上
            pre = pre.next;
        }
        //因为链表是有序的，所以将剩下的内容直接复制到pre.next即可
        if(l1 !=null){
            pre.next = l1;
        }else{
            pre.next =l2;
        }
        return dummy.next;
    }
    public static void main(String[] args){
        System.out.print(3&1);
    }
}
